/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.ssa;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import com.android.dx.rop.code.BasicBlock;
import com.android.dx.rop.code.BasicBlockList;
import com.android.dx.rop.code.Insn;
import com.android.dx.rop.code.InsnList;
import com.android.dx.rop.code.PlainInsn;
import com.android.dx.rop.code.RegisterSpec;
import com.android.dx.rop.code.RegisterSpecList;
import com.android.dx.rop.code.Rop;
import com.android.dx.rop.code.RopMethod;
import com.android.dx.rop.code.Rops;
import com.android.dx.rop.code.SourcePosition;
import com.android.dx.util.Hex;
import com.android.dx.util.IntList;
import com.android.dx.util.IntSet;

/**
 * An SSA representation of a basic block.
 */
public final class SsaBasicBlock {

	/**
	 * {@code non-null;} comparator for instances of this class that just
	 * compares block labels
	 */
	public static final Comparator<SsaBasicBlock> LABEL_COMPARATOR = new LabelComparator();

	/** {@code non-null;} insn list associated with this instance */
	private ArrayList<SsaInsn> insns;

	/** {@code non-null;} predecessor set (by block list index) */
	private BitSet predecessors;

	/** {@code non-null;} successor set (by block list index) */
	private BitSet successors;

	/**
	 * {@code non-null;} ordered successor list (same block may be listed more
	 * than once)
	 */
	private IntList successorList;

	/**
	 * block list index of primary successor, or {@code -1} for no primary
	 * successor
	 */
	private int primarySuccessor = -1;

	/** label of block in rop form */
	private int ropLabel;

	/** {@code non-null;} method we belong to */
	private SsaMethod parent;

	/** our index into parent.getBlock() */
	private int index;

	/** list of dom children */
	private final ArrayList<SsaBasicBlock> domChildren;

	/**
	 * the number of moves added to the end of the block during the phi-removal
	 * process. Retained for subsequent move scheduling.
	 */
	private int movesFromPhisAtEnd = 0;

	/**
	 * the number of moves added to the beginning of the block during the
	 * phi-removal process. Retained for subsequent move scheduling.
	 */
	private int movesFromPhisAtBeginning = 0;

	/**
	 * contains last computed value of reachability of this block, or -1 if
	 * reachability hasn't been calculated yet
	 */
	private int reachable = -1;

	/**
	 * {@code null-ok;} indexed by reg: the regs that are live-in at this block
	 */
	private IntSet liveIn;

	/**
	 * {@code null-ok;} indexed by reg: the regs that are live-out at this block
	 */
	private IntSet liveOut;

	/**
	 * Creates a new empty basic block.
	 * 
	 * @param basicBlockIndex
	 *            index this block will have
	 * @param ropLabel
	 *            original rop-form label
	 * @param parent
	 *            method of this block
	 */
	public SsaBasicBlock(final int basicBlockIndex, final int ropLabel,
			final SsaMethod parent) {
		this.parent = parent;
		this.index = basicBlockIndex;
		this.insns = new ArrayList<SsaInsn>();
		this.ropLabel = ropLabel;

		this.predecessors = new BitSet(parent.getBlocks().size());
		this.successors = new BitSet(parent.getBlocks().size());
		this.successorList = new IntList();

		domChildren = new ArrayList<SsaBasicBlock>();
	}

	/**
	 * Creates a new SSA basic block from a ROP form basic block.
	 * 
	 * @param rmeth
	 *            original method
	 * @param basicBlockIndex
	 *            index this block will have
	 * @param parent
	 *            method of this block predecessor set will be updated
	 * @return new instance
	 */
	public static SsaBasicBlock newFromRop(RopMethod rmeth,
			int basicBlockIndex, final SsaMethod parent) {
		BasicBlockList ropBlocks = rmeth.getBlocks();
		BasicBlock bb = ropBlocks.get(basicBlockIndex);
		SsaBasicBlock result = new SsaBasicBlock(basicBlockIndex,
				bb.getLabel(), parent);
		InsnList ropInsns = bb.getInsns();

		result.insns.ensureCapacity(ropInsns.size());

		for (int i = 0, sz = ropInsns.size(); i < sz; i++) {
			result.insns.add(new NormalSsaInsn(ropInsns.get(i), result));
		}

		result.predecessors = SsaMethod.bitSetFromLabelList(ropBlocks,
				rmeth.labelToPredecessors(bb.getLabel()));

		result.successors = SsaMethod.bitSetFromLabelList(ropBlocks,
				bb.getSuccessors());

		result.successorList = SsaMethod.indexListFromLabelList(ropBlocks,
				bb.getSuccessors());

		if (result.successorList.size() != 0) {
			int primarySuccessor = bb.getPrimarySuccessor();

			result.primarySuccessor = (primarySuccessor < 0) ? -1 : ropBlocks
					.indexOfLabel(primarySuccessor);
		}

		return result;
	}

	/**
	 * Adds a basic block as a dom child for this block. Used when constructing
	 * the dom tree.
	 * 
	 * @param child
	 *            {@code non-null;} new dom child
	 */
	public void addDomChild(SsaBasicBlock child) {
		domChildren.add(child);
	}

	/**
	 * Gets the dom children for this node. Don't modify this list.
	 * 
	 * @return {@code non-null;} list of dom children
	 */
	public ArrayList<SsaBasicBlock> getDomChildren() {
		return domChildren;
	}

	/**
	 * Adds a phi insn to the beginning of this block. The result type of the
	 * phi will be set to void, to indicate that it's currently unknown.
	 * 
	 * @param reg
	 *            {@code >=0;} result reg
	 */
	public void addPhiInsnForReg(int reg) {
		insns.add(0, new PhiInsn(reg, this));
	}

	/**
	 * Adds a phi insn to the beginning of this block. This is to be used when
	 * the result type or local-association can be determined at phi insert
	 * time.
	 * 
	 * @param resultSpec
	 *            {@code non-null;} reg
	 */
	public void addPhiInsnForReg(RegisterSpec resultSpec) {
		insns.add(0, new PhiInsn(resultSpec, this));
	}

	/**
	 * Adds an insn to the head of this basic block, just after any phi insns.
	 * 
	 * @param insn
	 *            {@code non-null;} rop-form insn to add
	 */
	public void addInsnToHead(Insn insn) {
		SsaInsn newInsn = SsaInsn.makeFromRop(insn, this);
		insns.add(getCountPhiInsns(), newInsn);
		parent.onInsnAdded(newInsn);
	}

	/**
	 * Replaces the last insn in this block. The provided insn must have some
	 * branchingness.
	 * 
	 * @param insn
	 *            {@code non-null;} rop-form insn to add, which must branch.
	 */
	public void replaceLastInsn(Insn insn) {
		if (insn.getOpcode().getBranchingness() == Rop.BRANCH_NONE) {
			throw new IllegalArgumentException("last insn must branch");
		}

		SsaInsn oldInsn = insns.get(insns.size() - 1);
		SsaInsn newInsn = SsaInsn.makeFromRop(insn, this);

		insns.set(insns.size() - 1, newInsn);

		parent.onInsnRemoved(oldInsn);
		parent.onInsnAdded(newInsn);
	}

	/**
	 * Visits each phi insn.
	 * 
	 * @param v
	 *            {@code non-null;} the callback
	 */
	public void forEachPhiInsn(PhiInsn.Visitor v) {
		int sz = insns.size();

		for (int i = 0; i < sz; i++) {
			SsaInsn insn = insns.get(i);
			if (insn instanceof PhiInsn) {
				v.visitPhiInsn((PhiInsn) insn);
			} else {
				/*
				 * Presently we assume PhiInsn's are in a continuous block at
				 * the top of the list
				 */
				break;
			}
		}
	}

	/**
	 * Deletes all phi insns. Do this after adding appropriate move insns.
	 */
	public void removeAllPhiInsns() {
		/*
		 * Presently we assume PhiInsn's are in a continuous block at the top of
		 * the list.
		 */

		insns.subList(0, getCountPhiInsns()).clear();
	}

	/**
	 * Gets the number of phi insns at the top of this basic block.
	 * 
	 * @return count of phi insns
	 */
	private int getCountPhiInsns() {
		int countPhiInsns;

		int sz = insns.size();
		for (countPhiInsns = 0; countPhiInsns < sz; countPhiInsns++) {
			SsaInsn insn = insns.get(countPhiInsns);
			if (!(insn instanceof PhiInsn)) {
				break;
			}
		}

		return countPhiInsns;
	}

	/**
	 * @return {@code non-null;} the (mutable) instruction list for this block,
	 *         with phi insns at the beginning
	 */
	public ArrayList<SsaInsn> getInsns() {
		return insns;
	}

	/**
	 * @return {@code non-null;} the (mutable) list of phi insns for this block
	 */
	public List<SsaInsn> getPhiInsns() {
		return insns.subList(0, getCountPhiInsns());
	}

	/**
	 * @return the block index of this block
	 */
	public int getIndex() {
		return index;
	}

	/**
	 * @return the label of this block in rop form
	 */
	public int getRopLabel() {
		return ropLabel;
	}

	/**
	 * @return the label of this block in rop form as a hex string
	 */
	public String getRopLabelString() {
		return Hex.u2(ropLabel);
	}

	/**
	 * @return {@code non-null;} predecessors set, indexed by block index
	 */
	public BitSet getPredecessors() {
		return predecessors;
	}

	/**
	 * @return {@code non-null;} successors set, indexed by block index
	 */
	public BitSet getSuccessors() {
		return successors;
	}

	/**
	 * @return {@code non-null;} ordered successor list, containing block
	 *         indicies
	 */
	public IntList getSuccessorList() {
		return successorList;
	}

	/**
	 * @return {@code >= -1;} block index of primary successor or {@code -1} if
	 *         no primary successor
	 */
	public int getPrimarySuccessorIndex() {
		return primarySuccessor;
	}

	/**
	 * @return rop label of primary successor
	 */
	public int getPrimarySuccessorRopLabel() {
		return parent.blockIndexToRopLabel(primarySuccessor);
	}

	/**
	 * @return {@code null-ok;} the primary successor block or {@code null} if
	 *         there is none
	 */
	public SsaBasicBlock getPrimarySuccessor() {
		if (primarySuccessor < 0) {
			return null;
		} else {
			return parent.getBlocks().get(primarySuccessor);
		}
	}

	/**
	 * @return successor list of rop labels
	 */
	public IntList getRopLabelSuccessorList() {
		IntList result = new IntList(successorList.size());

		int sz = successorList.size();

		for (int i = 0; i < sz; i++) {
			result.add(parent.blockIndexToRopLabel(successorList.get(i)));
		}
		return result;
	}

	/**
	 * @return {@code non-null;} method that contains this block
	 */
	public SsaMethod getParent() {
		return parent;
	}

	/**
	 * Inserts a new empty GOTO block as a predecessor to this block. All
	 * previous predecessors will be predecessors to the new block.
	 * 
	 * @return {@code non-null;} an appropriately-constructed instance
	 */
	public SsaBasicBlock insertNewPredecessor() {
		SsaBasicBlock newPred = parent.makeNewGotoBlock();

		// Update the new block.
		newPred.predecessors = predecessors;
		newPred.successors.set(index);
		newPred.successorList.add(index);
		newPred.primarySuccessor = index;

		// Update us.
		predecessors = new BitSet(parent.getBlocks().size());
		predecessors.set(newPred.index);

		// Update our (soon-to-be) old predecessors.
		for (int i = newPred.predecessors.nextSetBit(0); i >= 0; i = newPred.predecessors
				.nextSetBit(i + 1)) {

			SsaBasicBlock predBlock = parent.getBlocks().get(i);

			predBlock.replaceSuccessor(index, newPred.index);
		}

		return newPred;
	}

	/**
	 * Constructs and inserts a new empty GOTO block {@code Z} between this
	 * block ({@code A}) and a current successor block ({@code B}). The new
	 * block will replace B as A's successor and A as B's predecessor. A and B
	 * will no longer be directly connected. If B is listed as a successor
	 * multiple times, all references are replaced.
	 * 
	 * @param other
	 *            current successor (B)
	 * @return {@code non-null;} an appropriately-constructed instance
	 */
	public SsaBasicBlock insertNewSuccessor(SsaBasicBlock other) {
		SsaBasicBlock newSucc = parent.makeNewGotoBlock();

		if (!successors.get(other.index)) {
			throw new RuntimeException("Block " + other.getRopLabelString()
					+ " not successor of " + getRopLabelString());
		}

		// Update the new block.
		newSucc.predecessors.set(this.index);
		newSucc.successors.set(other.index);
		newSucc.successorList.add(other.index);
		newSucc.primarySuccessor = other.index;

		// Update us.
		for (int i = successorList.size() - 1; i >= 0; i--) {
			if (successorList.get(i) == other.index) {
				successorList.set(i, newSucc.index);
			}
		}

		if (primarySuccessor == other.index) {
			primarySuccessor = newSucc.index;
		}
		successors.clear(other.index);
		successors.set(newSucc.index);

		// Update "other".
		other.predecessors.set(newSucc.index);
		other.predecessors.set(index, successors.get(other.index));

		return newSucc;
	}

	/**
	 * Replaces an old successor with a new successor. This will throw
	 * RuntimeException if {@code oldIndex} was not a successor.
	 * 
	 * @param oldIndex
	 *            index of old successor block
	 * @param newIndex
	 *            index of new successor block
	 */
	public void replaceSuccessor(int oldIndex, int newIndex) {
		if (oldIndex == newIndex) {
			return;
		}

		// Update us.
		successors.set(newIndex);

		if (primarySuccessor == oldIndex) {
			primarySuccessor = newIndex;
		}

		for (int i = successorList.size() - 1; i >= 0; i--) {
			if (successorList.get(i) == oldIndex) {
				successorList.set(i, newIndex);
			}
		}

		successors.clear(oldIndex);

		// Update new successor.
		parent.getBlocks().get(newIndex).predecessors.set(index);

		// Update old successor.
		parent.getBlocks().get(oldIndex).predecessors.clear(index);
	}

	/**
	 * Removes a successor from this block's successor list.
	 * 
	 * @param oldIndex
	 *            index of successor block to remove
	 */
	public void removeSuccessor(int oldIndex) {
		int removeIndex = 0;

		for (int i = successorList.size() - 1; i >= 0; i--) {
			if (successorList.get(i) == oldIndex) {
				removeIndex = i;
			} else {
				primarySuccessor = successorList.get(i);
			}
		}

		successorList.removeIndex(removeIndex);
		successors.clear(oldIndex);
		parent.getBlocks().get(oldIndex).predecessors.clear(index);
	}

	/**
	 * Attaches block to an exit block if necessary. If this block is not an
	 * exit predecessor or is the exit block, this block does nothing. For use
	 * by {@link com.android.dx.ssa.SsaMethod#makeExitBlock}
	 * 
	 * @param exitBlock
	 *            {@code non-null;} exit block
	 */
	public void exitBlockFixup(SsaBasicBlock exitBlock) {
		if (this == exitBlock) {
			return;
		}

		if (successorList.size() == 0) {
			/*
			 * This is an exit predecessor. Set the successor to the exit block
			 */
			successors.set(exitBlock.index);
			successorList.add(exitBlock.index);
			primarySuccessor = exitBlock.index;
			exitBlock.predecessors.set(this.index);
		}
	}

	/**
	 * Adds a move instruction to the end of this basic block, just before the
	 * last instruction. If the result of the final instruction is the source in
	 * question, then the move is placed at the beginning of the primary
	 * successor block. This is for unversioned registers.
	 * 
	 * @param result
	 *            move destination
	 * @param source
	 *            move source
	 */
	public void addMoveToEnd(RegisterSpec result, RegisterSpec source) {

		if (result.getReg() == source.getReg()) {
			// Sometimes we end up with no-op moves. Ignore them here.
			return;
		}

		/*
		 * The last Insn has to be a normal SSA insn: a phi can't branch or
		 * return or cause an exception, etc.
		 */
		NormalSsaInsn lastInsn;
		lastInsn = (NormalSsaInsn) insns.get(insns.size() - 1);

		if (lastInsn.getResult() != null || lastInsn.getSources().size() > 0) {
			/*
			 * The final insn in this block has a source or result register, and
			 * the moves we may need to place and schedule may interfere. We
			 * need to insert this instruction at the beginning of the primary
			 * successor block instead. We know this is safe, because when we
			 * edge-split earlier, we ensured that each successor has only us as
			 * a predecessor.
			 */

			for (int i = successors.nextSetBit(0); i >= 0; i = successors
					.nextSetBit(i + 1)) {

				SsaBasicBlock succ;

				succ = parent.getBlocks().get(i);
				succ.addMoveToBeginning(result, source);
			}
		} else {
			/*
			 * We can safely add a move to the end of the block just before the
			 * last instruction, because the final insn does not assign to
			 * anything.
			 */
			RegisterSpecList sources = RegisterSpecList.make(source);
			NormalSsaInsn toAdd = new NormalSsaInsn(new PlainInsn(
					Rops.opMove(result.getType()), SourcePosition.NO_INFO,
					result, sources), this);

			insns.add(insns.size() - 1, toAdd);

			movesFromPhisAtEnd++;
		}
	}

	/**
	 * Adds a move instruction after the phi insn block.
	 * 
	 * @param result
	 *            move destination
	 * @param source
	 *            move source
	 */
	public void addMoveToBeginning(RegisterSpec result, RegisterSpec source) {
		if (result.getReg() == source.getReg()) {
			// Sometimes we end up with no-op moves. Ignore them here.
			return;
		}

		RegisterSpecList sources = RegisterSpecList.make(source);
		NormalSsaInsn toAdd = new NormalSsaInsn(new PlainInsn(
				Rops.opMove(result.getType()), SourcePosition.NO_INFO, result,
				sources), this);

		insns.add(getCountPhiInsns(), toAdd);
		movesFromPhisAtBeginning++;
	}

	/**
	 * Sets the register as used in a bitset, taking into account its
	 * category/width.
	 * 
	 * @param regsUsed
	 *            set, indexed by register number
	 * @param rs
	 *            register to mark as used
	 */
	private static void setRegsUsed(BitSet regsUsed, RegisterSpec rs) {
		regsUsed.set(rs.getReg());
		if (rs.getCategory() > 1) {
			regsUsed.set(rs.getReg() + 1);
		}
	}

	/**
	 * Checks to see if the register is used in a bitset, taking into account
	 * its category/width.
	 * 
	 * @param regsUsed
	 *            set, indexed by register number
	 * @param rs
	 *            register to mark as used
	 * @return true if register is fully or partially (for the case of wide
	 *         registers) used.
	 */
	private static boolean checkRegUsed(BitSet regsUsed, RegisterSpec rs) {
		int reg = rs.getReg();
		int category = rs.getCategory();

		return regsUsed.get(reg)
				|| (category == 2 ? regsUsed.get(reg + 1) : false);
	}

	/**
	 * Ensures that all move operations in this block occur such that reads of
	 * any register happen before writes to that register. NOTE: caller is
	 * expected to returnSpareRegisters()! TODO: See Briggs, et al "Practical
	 * Improvements to the Construction and Destruction of Static Single
	 * Assignment Form" section 5. a) This can be done in three passes.
	 * 
	 * @param toSchedule
	 *            List of instructions. Must consist only of moves.
	 */
	private void scheduleUseBeforeAssigned(List<SsaInsn> toSchedule) {
		BitSet regsUsedAsSources = new BitSet(parent.getRegCount());

		// TODO: Get rid of this.
		BitSet regsUsedAsResults = new BitSet(parent.getRegCount());

		int sz = toSchedule.size();

		int insertPlace = 0;

		while (insertPlace < sz) {
			int oldInsertPlace = insertPlace;

			// Record all registers used as sources in this block.
			for (int i = insertPlace; i < sz; i++) {
				setRegsUsed(regsUsedAsSources, toSchedule.get(i).getSources()
						.get(0));

				setRegsUsed(regsUsedAsResults, toSchedule.get(i).getResult());
			}

			/*
			 * If there are no circular dependencies, then there exists n
			 * instructions where n > 1 whose result is not used as a source.
			 */
			for (int i = insertPlace; i < sz; i++) {
				SsaInsn insn = toSchedule.get(i);

				/*
				 * Move these n registers to the front, since they overwrite
				 * nothing.
				 */
				if (!checkRegUsed(regsUsedAsSources, insn.getResult())) {
					Collections.swap(toSchedule, i, insertPlace++);
				}
			}

			/*
			 * If we've made no progress in this iteration, there's a circular
			 * dependency. Split it using the temp reg.
			 */
			if (oldInsertPlace == insertPlace) {

				SsaInsn insnToSplit = null;

				// Find an insn whose result is used as a source.
				for (int i = insertPlace; i < sz; i++) {
					SsaInsn insn = toSchedule.get(i);
					if (checkRegUsed(regsUsedAsSources, insn.getResult())
							&& checkRegUsed(regsUsedAsResults, insn
									.getSources().get(0))) {

						insnToSplit = insn;
						/*
						 * We're going to split this insn; move it to the front.
						 */
						Collections.swap(toSchedule, insertPlace, i);
						break;
					}
				}

				// At least one insn will be set above.

				RegisterSpec result = insnToSplit.getResult();
				RegisterSpec tempSpec = result.withReg(parent
						.borrowSpareRegister(result.getCategory()));

				NormalSsaInsn toAdd = new NormalSsaInsn(new PlainInsn(
						Rops.opMove(result.getType()), SourcePosition.NO_INFO,
						tempSpec, insnToSplit.getSources()), this);

				toSchedule.add(insertPlace++, toAdd);

				RegisterSpecList newSources = RegisterSpecList.make(tempSpec);

				NormalSsaInsn toReplace = new NormalSsaInsn(new PlainInsn(
						Rops.opMove(result.getType()), SourcePosition.NO_INFO,
						result, newSources), this);

				toSchedule.set(insertPlace, toReplace);

				// The size changed.
				sz = toSchedule.size();
			}

			regsUsedAsSources.clear();
			regsUsedAsResults.clear();
		}
	}

	/**
	 * Adds {@code regV} to the live-out list for this block. This is called by
	 * the liveness analyzer.
	 * 
	 * @param regV
	 *            register that is live-out for this block.
	 */
	public void addLiveOut(int regV) {
		if (liveOut == null) {
			liveOut = SetFactory.makeLivenessSet(parent.getRegCount());
		}

		liveOut.add(regV);
	}

	/**
	 * Adds {@code regV} to the live-in list for this block. This is called by
	 * the liveness analyzer.
	 * 
	 * @param regV
	 *            register that is live-in for this block.
	 */
	public void addLiveIn(int regV) {
		if (liveIn == null) {
			liveIn = SetFactory.makeLivenessSet(parent.getRegCount());
		}

		liveIn.add(regV);
	}

	/**
	 * Returns the set of live-in registers. Valid after register interference
	 * graph has been generated, otherwise empty.
	 * 
	 * @return {@code non-null;} live-in register set.
	 */
	public IntSet getLiveInRegs() {
		if (liveIn == null) {
			liveIn = SetFactory.makeLivenessSet(parent.getRegCount());
		}
		return liveIn;
	}

	/**
	 * Returns the set of live-out registers. Valid after register interference
	 * graph has been generated, otherwise empty.
	 * 
	 * @return {@code non-null;} live-out register set
	 */
	public IntSet getLiveOutRegs() {
		if (liveOut == null) {
			liveOut = SetFactory.makeLivenessSet(parent.getRegCount());
		}
		return liveOut;
	}

	/**
	 * @return true if this is the one-and-only exit block for this method
	 */
	public boolean isExitBlock() {
		return index == parent.getExitBlockIndex();
	}

	/**
	 * Returns true if this block was last calculated to be reachable.
	 * Recalculates reachability if value has never been computed.
	 * 
	 * @return {@code true} if reachable
	 */
	public boolean isReachable() {
		if (reachable == -1) {
			parent.computeReachability();
		}
		return (reachable == 1);
	}

	/**
	 * Sets reachability of block to specified value
	 * 
	 * @param reach
	 *            new value of reachability for block
	 */
	public void setReachable(int reach) {
		reachable = reach;
	}

	/**
	 * Sorts move instructions added via {@code addMoveToEnd} during phi removal
	 * so that results don't overwrite sources that are used. For use after all
	 * phis have been removed and all calls to addMoveToEnd() have been made.
	 * <p>
	 * This is necessary because copy-propogation may have left us in a state
	 * where the same basic block has the same register as a phi operand and a
	 * result. In this case, the register in the phi operand always refers value
	 * before any other phis have executed.
	 */
	public void scheduleMovesFromPhis() {
		if (movesFromPhisAtBeginning > 1) {
			List<SsaInsn> toSchedule;

			toSchedule = insns.subList(0, movesFromPhisAtBeginning);

			scheduleUseBeforeAssigned(toSchedule);

			SsaInsn firstNonPhiMoveInsn = insns.get(movesFromPhisAtBeginning);

			/*
			 * TODO: It's actually possible that this case never happens,
			 * because a move-exception block, having only one predecessor in
			 * SSA form, perhaps is never on a dominance frontier.
			 */
			if (firstNonPhiMoveInsn.isMoveException()) {
				if (true) {
					/*
					 * We've yet to observe this case, and if it can occur the
					 * code written to handle it probably does not work.
					 */
					throw new RuntimeException("Unexpected: moves from "
							+ "phis before move-exception");
				} else {
					/*
					 * A move-exception insn must be placed first in this block
					 * We need to move it there, and deal with possible
					 * interference.
					 */
					boolean moveExceptionInterferes = false;

					int moveExceptionResult = firstNonPhiMoveInsn.getResult()
							.getReg();

					/*
					 * Does the move-exception result reg interfere with the phi
					 * moves?
					 */
					for (SsaInsn insn : toSchedule) {
						if (insn.isResultReg(moveExceptionResult)
								|| insn.isRegASource(moveExceptionResult)) {
							moveExceptionInterferes = true;
							break;
						}
					}

					if (!moveExceptionInterferes) {
						// This is the easy case.
						insns.remove(movesFromPhisAtBeginning);
						insns.add(0, firstNonPhiMoveInsn);
					} else {
						/*
						 * We need to move the result to a spare reg and move it
						 * back.
						 */
						RegisterSpec originalResultSpec = firstNonPhiMoveInsn
								.getResult();
						int spareRegister = parent
								.borrowSpareRegister(originalResultSpec
										.getCategory());

						// We now move it to a spare register.
						firstNonPhiMoveInsn.changeResultReg(spareRegister);
						RegisterSpec tempSpec = firstNonPhiMoveInsn.getResult();

						insns.add(0, firstNonPhiMoveInsn);

						// And here we move it back.

						NormalSsaInsn toAdd = new NormalSsaInsn(new PlainInsn(
								Rops.opMove(tempSpec.getType()),
								SourcePosition.NO_INFO, originalResultSpec,
								RegisterSpecList.make(tempSpec)), this);

						/*
						 * Place it immediately after the phi-moves, overwriting
						 * the move-exception that was there.
						 */
						insns.set(movesFromPhisAtBeginning + 1, toAdd);
					}
				}
			}
		}

		if (movesFromPhisAtEnd > 1) {
			scheduleUseBeforeAssigned(insns.subList(insns.size()
					- movesFromPhisAtEnd - 1, insns.size() - 1));
		}

		// Return registers borrowed here and in scheduleUseBeforeAssigned().
		parent.returnSpareRegisters();

	}

	/**
	 * Visits all insns in this block.
	 * 
	 * @param visitor
	 *            {@code non-null;} callback interface
	 */
	public void forEachInsn(SsaInsn.Visitor visitor) {
		// This gets called a LOT, and not using an iterator
		// saves a lot of allocations and reduces memory usage
		int len = insns.size();
		for (int i = 0; i < len; i++) {
			insns.get(i).accept(visitor);
		}
	}

	/** {@inheritDoc} */
	@Override
	public String toString() {
		return "{" + index + ":" + Hex.u2(ropLabel) + '}';
	}

	/**
	 * Visitor interface for basic blocks.
	 */
	public interface Visitor {

		/**
		 * Indicates a block has been visited by an iterator method.
		 * 
		 * @param v
		 *            {@code non-null;} block visited
		 * @param parent
		 *            {@code null-ok;} parent node if applicable
		 */
		void visitBlock(SsaBasicBlock v, SsaBasicBlock parent);
	}

	/**
	 * Label comparator.
	 */
	public static final class LabelComparator implements
			Comparator<SsaBasicBlock> {

		/** {@inheritDoc} */
		public int compare(SsaBasicBlock b1, SsaBasicBlock b2) {
			int label1 = b1.ropLabel;
			int label2 = b2.ropLabel;

			if (label1 < label2) {
				return -1;
			} else if (label1 > label2) {
				return 1;
			} else {
				return 0;
			}
		}
	}
}
